class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 返回节点的值
class Solution(object):
    def plusOne(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        out = []
        while head:
            out.append(head.val)
            head = head.next
        index = len(out) - 1
        while index >= 0 and out[index] + 1 > 9:
            out[index] = 0
            index -= 1
        if index >= 0:
            out[index] += 1
        else:
            out.insert(0, 1)
        return out

# 返回链表
class Solution(object):
    def plusOne(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        def search(node):
            if node.next:
                cond = search(node.next)
                if not cond:
                    return 0
                else:
                    if node.val + 1 < 10:
                        node.val += 1
                        return 0
                    else:
                        node.val = 0
                        return 1

            else:
                if node.val + 1 < 10:
                    node.val += 1
                    return 0
                else:
                    node.val = 0
                    return 1

        cond = search(head)
        if not cond:
            return head
        else:
            return ListNode(1, head)